\subsection{Categories}
\begin{definition}
    A \emph{category} \( \mathcal C \) consists of
    \begin{enumerate}
        \item a collection of \emph{objects} \( \ob \mathcal C \), denoted \( A, B, C, \dots \);
        \item a collection of \emph{morphisms} \( \mor \mathcal C \), denoted \( f, g, h, \dots \);
        \item two operations \( \dom, \cod : \mor \mathcal C \to \ob \mathcal C \), and we write \( f : A \to B \) or \( A \xrightarrow f B \) to state that \( f \) is a morphism with domain \( A \) and codomain \( B \);
        \item an operation \( A \mapsto 1_A : A \to A \);
        \item a \emph{composition} operation \( (f, g) \mapsto fg : \dom g \to \cod f \), defined exactly when \( \cod g = \dom f \); satisfying
        \item \( f 1_A = f \) and \( 1_A g = g \) whenever the composites are defined; and
        \item \( (fg)h = f(gh) \) whenever the composites are defined.
    \end{enumerate}
\end{definition}
\begin{remark}
    \begin{enumerate}
        \item The collections of objects and morphisms may be sets or classes in some set theory, but our definitions are built to be interpretable in any system supporting first-order logic.
        If \( \ob \mathcal C \) and \( \mor \mathcal C \) are sets, we call \( \mathcal C \) a \emph{small} category; otherwise we call it \emph{large}.
        \item We could formulate a definition of category with no mention of objects, since objects biject with the identity morphisms.
        We will not take this approach here.
        \item Note that we choose \( fg \) to mean `first \( g \) and then \( f \)'; this choice is a convention and the other one may be adopted.
    \end{enumerate}
\end{remark}
\begin{example}
    \begin{enumerate}
        \item \( \mathbf{Set} \) is the category where the objects are all of the sets, and the morphisms are all of the functions between them, each of which is suitably tagged with an appropriate codomain.
        This must be done because set-theoretic functions do not `remember' their codomain: \( f(x) = x \) as a function \( f : \mathbb R \to \mathbb R \) or \( \mathbb R \to \mathbb C \) are equal sets.
        \item \( \mathbf{Gp} \) is the category where the objects are all of the groups, and the morphisms are all of the group homomorphisms.
        \item \( \mathbf{Rng} \) is the category where the objects are all of the rings, and the morphisms are all of the ring homomorphisms.
        \item For a field \( k \), \( \mathbf{Vect}_k \) is the category where the objects are all of the \( k \)-vector spaces, and the morphisms are all of the \( k \)-linear maps.
        \item \( \mathbf{Top} \) is the category where the objects are all of the topological spaces, and the morphisms are all of the continuous functions.
        \item \( \mathbf{Met} \) is the category where the objects are all of the metric spaces, and the morphisms are all of the nonexpansive mappings, i.e.\ functions that do not increase the distance between points.
        One could choose a different convention, for example by letting morphisms be arbitrary continuous functions.
        \item \( \mathbf{Mfd} \) is the category where the objects are all of the smooth manifolds, and the morphisms are \( C^\infty \) maps.
        \item \( \mathbf{TopGp} \) is the category where the objects are all of the topological groups, and the morphisms are the continuous homomorphisms.
        \item \( \mathbf{Htpy} \) is the category where the objects are all of the topological spaces, and the morphisms are equivalence classes of continuous functions under homotopy.
        \item More generally, if \( \simeq \) is an equivalence relation on the morphisms of \( \mathcal C \) such that \( f \simeq g \) implies \( \dom f = \dom g \) and \( \cod f = \cod g \), and the relation is stable under composition so \( f \simeq g \) implies \( fh \simeq gh \) and \( kf \simeq kg \), we call \( \simeq \) a \emph{congruence}.
        In this case, we can form the \emph{quotient category} \( \faktor{\mathcal C}{\simeq} \), which has the same objects as \( \mathcal C \), but its objects are equivalence classes of morphisms in \( \mathcal C \) under \( \simeq \).
        \item \( \mathbf{Rel} \) is the category where the objects are all of the sets, and the morphisms \( A \to B \) are the relations \( R \subseteq A \times B \), where composition is given by
        \[ S \circ R = \qty{(a, c) \mid \exists b \in B, (a, b) \in R \wedge (b, c) \in S} \]
        Note that if \( R \) and \( S \) happen to be functions, \( \circ \) is the standard composition operator.
        Therefore, \( \mathbf{Set} \) is a subcategory of \( \mathbf{Rel} \).
        \item \( \mathbf{Part} \) is the category where the objects are all of the sets, and the morphisms \( A \to B \) are the partial functions \( A \rightharpoonup B \).
        This is a subcategory of \( \mathbf{Rel} \), and \( \mathbf{Set} \) is a subcategory of \( \mathbf{Part} \).
        \item Given a category \( \mathcal C \), we can construct its \emph{opposite category} \( \mathcal C^\cop \), where the objects and morphisms are the same as in \( \mathcal C \), but \( \dom \) and \( \cod \) are swapped.
        We also reverse composition in the opposite category.
        This gives a duality principle: whenever a statement about categories is proven, a dual statement follows from applying the statement to an opposite category.
        \item A small category with one object \( \star \) is a \emph{monoid}, a group without inverses.
        In particular, every group can be seen as a small category on a single object in which every morphism is an isomorphism, i.e.\ invertible.
        \item A \emph{groupoid} is a category in which every morphism is an isomorphism.
        For example, we can construct the \emph{fundamental groupoid} of a topological space \( X \).
        Here, the objects correspond to points \( x \) in \( X \), and represent \( \pi_1(X, x) \).
        Morphisms \( x \to y \) are homotopy classes of paths starting at \( x \) and ending at \( y \).
        Composition is path concatenation.
        \item A category with at most one morphism between any pair of objects is a \emph{preorder}.
        The existence of a morphism \( A \to B \) corresponds to stating \( A \preceq B \) in the preorder.
        In particular, a partially ordered set (poset) is a small preorder in which the only isomorphisms are identity morphisms.
        \item For a field \( k \), \( \mathbf{Mat}_k \) is the category where the objects are the natural numbers, and the morphisms \( n \to p \) are the \( p \times n \) matrices over \( k \).
        Composition is multiplication of matrices.
        The identity morphisms are the identity matrices.
    \end{enumerate}
\end{example}

\subsection{Functors}
\begin{definition}
    Let \( \mathcal C, \mathcal D \) be categories.
    A \emph{functor} \( F : \mathcal C \to \mathcal D \) consists of a map \( \ob \mathcal C \xrightarrow F \ob \mathcal D \) and a map \( \mor \mathcal C \xrightarrow F \mor \mathcal D \), such that
    \begin{enumerate}
        \item \( F(\dom f) = \dom Ff \);
        \item \( F(\cod f) = \cod Ff \);
        \item \( F(1_A) = 1_{F A} \); and
        \item \( F(fg) = (Ff)(Fg) \) whenever \( fg \) is defined.
    \end{enumerate}
\end{definition}
\begin{example}
    \begin{enumerate}
        \item The \emph{forgetful functors} \( \mathbf{Gp} \to \mathbf{Set}, \mathbf{Rng} \to \mathbf{Set}, \mathbf{Top} \to \mathbf{Set} \) and so on forget that the objects are structures and forget the conditions on morphisms.
        Similarly, there are forgetful functors \( \mathbf{Rng} \to \mathbf{AbGp}, \mathbf{Met} \to \mathbf{Top}, \mathbf{TopGp} \to \mathbf{Top}, \mathbf{TopGp} \to \mathbf{Gp} \).
        \item Any mapping \( f : A \to UG \) from a set \( A \) to the underlying set of a group \( G \) extends uniquely to a homomorphism \( FA \to G \), where \( FA \) is the free group on the set \( A \).
        This can be made into a functor \( F : \mathbf{Set} \to \mathbf{Gp} \): given \( f : A \to B \), the homomorphism \( Ff \) is the unique homomorphism extending \( A \xrightarrow f B \to FB \).
        Given \( g : B \to C \), then \( F(gf) \) and \( (Fg)(Ff) \) both extend the same mapping \( A \to FC \), so by the uniqueness property they are equal.
        \item The power-set construction \( P : \mathbf{Set} \to \mathbf{Set} \) is a functor.
        \( PA \) is the set of all subsets of \( A \), and given \( f : A \to B \), \( Pf \) is the map sending \( S \) to the image of \( S \) under \( f \).
        \item There is another power-set functor \( P^\star : \mathbf{Set}^\cop \to \mathbf{Set} \) (or \( \mathbf{Set} \to \mathbf{Set}^\cop \)).
        This has the same object map, but given \( f : A \to B \), \( P^\star f \) maps \( S \subseteq B \) to its inverse image under \( f \).
        A functor like this that reverses the direction of arrows is sometimes called \emph{contravariant}; functors which do not are called \emph{covariant}.
        \item The construction of dual spaces in linear algebra gives rise to a functor \( (-)^\star : \mathbf{Vect}_k^\cop \to \mathbf{Vect}_k \).
        \( V^\star \) is the space of linear maps \( V \to k \), and a linear map \( f : V \to W \) gives rise to \( f^\star : W^\star \to V^\star \) given by composition.
        \item \( \mathbf{Cat} \) is the category where the objects are the small categories and the morphisms are functors.
        This is well-defined as functors have identities and compositions.
        \item The assignment \( \mathcal C \to \mathcal C^\cop \) defines a (covariant) functor \( \mathbf{Cat} \to \mathbf{Cat} \).
        \item A functor between monoids is a monoid homomorphism.
        \item A functor between groups is a group homomorphism.
        \item A functor between posets is an order-preserving map.
        \item If \( G \) is a group, a functor \( F : G \to \mathbf{Set} \) defines a set \( A = F \star \), together with a collection of endomorphisms of \( A \) denoted \( a \mapsto g \cdot a \) for each \( g \in G \).
        This collection of endomorphisms is compatible with the identity and composition, so is precisely the definition of a group action or permutation representation of \( G \).
        \item If \( G \) is a group, a functor \( F : G \to \mathbf{Vect}_k \) is a \( k \)-linear representation of \( G \).
        \item The fundamental group of a topological space defines a functor \( \pi_1 : \mathbf{Top}_\star \to \mathbf{Gp} \), where \( \mathbf{Top}_\star \) is the category of pointed topological spaces.
    \end{enumerate}
\end{example}

\subsection{Natural transformations}
\begin{definition}
    Let \( \mathcal C, \mathcal D \) be categories, and \( F, G : \mathcal C \rightrightarrows \mathcal D \) be functors.
    A \emph{natural transformation} \( \alpha : F \to G \) is a mapping \( \ob \mathcal C \to \mor \mathcal D \) denoted \( A \mapsto \alpha_A \), such that
    \begin{enumerate}
        \item \( \alpha_A : FA \to GA \) for all \( A \); and
        \item for any morphism \( f : A \to B \) in \( \mathcal C \), the square
        \[\begin{tikzcd}
            FA & FB \\
            GA & GB
            \arrow["Ff", from=1-1, to=1-2]
            \arrow["{\alpha_B}", from=1-2, to=2-2]
            \arrow["{\alpha_A}"', from=1-1, to=2-1]
            \arrow["Gf"', from=2-1, to=2-2]
        \end{tikzcd}\]
        commutes.
        Such squares are called \emph{naturality} squares.
    \end{enumerate}
\end{definition}
If we have a natural transformation \( \beta : G \to H \), we can define \( \beta \alpha \) by \( (\beta \alpha)_A = \beta_A \alpha_A \).
We therefore have a category \( [\mathcal C, \mathcal D] \) whose objects are the functors \( \mathcal C \to \mathcal D \) and whose morphisms are the natural transformations between them.
\begin{example}
    \begin{enumerate}
        \item Given a vector space \( V \), we have a linear map \( \alpha_V : V \to V^{\star\star} \) sending \( v \in V \) to the map \( f \mapsto f(v) \).
        This is a natural transformation \( \alpha : 1_{\mathbf{Vect}_k} \to (-)^{\star\star} \).
        The naturality squares are of the form
        % The fact that the naturality squares commute can be easily checked.
        \[\begin{tikzcd}
            V & W \\
            {V^{\star\star}} & {W^{\star\star}}
            \arrow["f", from=1-1, to=1-2]
            \arrow["{\alpha_W}", from=1-2, to=2-2]
            \arrow["{\alpha_V}"', from=1-1, to=2-1]
            \arrow["{f^{\star\star}}"', from=2-1, to=2-2]
        \end{tikzcd}\]
        where
        \[ \alpha_V(v) = f \mapsto f(v);\quad f^{\star\star}(g)(h) = g (f^\star h) = g (h \circ f) \]
        We show the naturality square commutes.
        \begin{align*}
            ((g \mapsto h \mapsto g(h \circ f)) \circ \alpha_V)(v) &= (g \mapsto h \mapsto g(h \circ f))(\alpha_V v) \\
            &= (g \mapsto h \mapsto g(h \circ f))(k \mapsto k v) \\
            &= h \mapsto (k \mapsto k v)(h \circ f) \\
            &= h \mapsto (h \circ f) v \\
            &= h \mapsto (h (fv)) \\
            &= \alpha_W (fv) \\
            &= (\alpha_W \circ f) v
        \end{align*}
        \item There is an inclusion from any set \( A \) to its free group \( FA \).
        The map sending a set \( A \) to the inclusion \( A \to FA \) is a natural transformation \( 1_{\mathbf{Set}} \to UF \).
        Naturality is built into the definition of \( F \) on morphisms.
        \[\begin{tikzcd}
            A & B \\
            UFA & UFB
            \arrow["f", from=1-1, to=1-2]
            \arrow["{\alpha_B}", from=1-2, to=2-2]
            \arrow["{\alpha_A}"', from=1-1, to=2-1]
            \arrow["{UF(f)}"', from=2-1, to=2-2]
        \end{tikzcd}\]
        \item There is a mapping \( \alpha_A : A \to PA \) by mapping \( a \in A \) to \( \qty{a} \in PA \).
        This is a natural transformation \( 1_{\mathbf{Set}} \to P \), since \( Pf\qty{a} = \qty{fa} \).
        \[\begin{tikzcd}
            A & B \\
            PA & PB
            \arrow["f", from=1-1, to=1-2]
            \arrow["{\alpha_B}", from=1-2, to=2-2]
            \arrow["{\alpha_A}"', from=1-1, to=2-1]
            \arrow["Pf"', from=2-1, to=2-2]
        \end{tikzcd}\]
        \item Let \( f, g : P \rightrightarrows Q \) be order-preserving maps between posets.
        Then for \( x \leq y \) in \( P \), the naturality square is
        \[\begin{tikzcd}
            fx & fy \\
            gx & gy
            \arrow["{\alpha_x}"', from=1-1, to=2-1]
            \arrow[from=2-1, to=2-2]
            \arrow["{\alpha_y}", from=1-2, to=2-2]
            \arrow[from=1-1, to=1-2]
        \end{tikzcd}\]
        In particular, the existence of \( \alpha_x \) proves that \( fx \leq gx \).
        Thus a natural transformation \( f \to g \) exists if and only if \( fx \leq gx \) pointwise for all \( x \in P \).
        Note that every commutative square in a poset commutes.
        \item Let \( u, v : G \rightrightarrows H \) be group homomorphisms.
        For \( g \in G \), the naturality square is
        \[\begin{tikzcd}
            \star & \star \\
            \star & \star
            \arrow["ug", from=1-1, to=1-2]
            \arrow["{\alpha_\star}", from=1-2, to=2-2]
            \arrow["{\alpha_\star}"', from=1-1, to=2-1]
            \arrow["vg"', from=2-1, to=2-2]
        \end{tikzcd}\]
        A natural transformation \( \alpha : u \to v \) is an element \( \alpha_\star = h \in H \) such that \( h u(g) = v(g) h \) for all \( g \), or equivalently, \( v(g) = h u(g) h^{-1} \).
        Thus a natural transformation exhibits a conjugacy between two homomorphisms.
        In particular, the natural transformations \( u \to u \) are the elements of the centraliser of \( u(G) \).
        \item Let \( A, B \) be permutation representations of \( G \), that is, functors \( G \to \mathbf{Set} \).
        \[\begin{tikzcd}
            A\star & A\star \\
            B\star & B\star
            \arrow["Ag", from=1-1, to=1-2]
            \arrow["f", from=1-2, to=2-2]
            \arrow["f"', from=1-1, to=2-1]
            \arrow["Bg"', from=2-1, to=2-2]
        \end{tikzcd}\]
        A natural transformation \( f : A \to B \) is a mapping of the underlying sets \( A\star \to B\star \) satisfying \( g \cdot f(a) = f(g \cdot a) \) for all \( a \in A \) and \( g \in G \).
        This is the definition of a \( G \)-equivariant map.
        \item For any (nice) pointed topological space \( X \) with base point \( x \), the \emph{Hurewicz homomorphism} is a map \( h_{n, x} : \pi_n(X, x) \to H_n(X) \).
        This is a natural transformation \( \pi_n \to H_n U \) where \( U \) is the forgetful functor \( \mathbf{Top}_\star \to \mathbf{Top} \).
    \end{enumerate}
\end{example}

\subsection{Equivalence of categories}
There is a notion of isomorphism of categories, namely, isomorphism in the category \( \mathbf{Cat} \).
For example, \( \mathbf{Rel} \cong \mathbf{Rel}^\cop \) via the functor
\[ A \mapsto A;\quad R \mapsto R^\circ = \qty{(b, a) \mid (a, b) \in R} \]
However, there is a weaker notion that is often more useful in practice, called equivalence.
To define this, we need a notion of `natural isomorphism'.
There are two obvious definitions, which we show are equivalent.
\begin{lemma}
    Let \( \alpha : F \to G \) be a natural transformation between functors \( \mathcal C \rightrightarrows \mathcal D \).
    Then \( \alpha \) is an isomorphism in the functor category \( [\mathcal C, \mathcal D] \) if and only if each component \( \alpha_A \) is an isomorphism in \( \mathcal D \).
\end{lemma}
\begin{proof}
    The forward direction is clear as composition in \( [\mathcal C, \mathcal D] \) is pointwise; if \( \beta \) is an inverse for \( \alpha \), then \( \beta_A \) is an inverse for \( \alpha_A \).
    Suppose \( \beta_A \) is an inverse for \( \alpha_A \) for each \( A \).
    We show the \( \beta \) collectively form a natural transformation by verifying the naturality squares.
    Given \( f : A \to B \) in \( \mathcal C \), consider
    \[\begin{tikzcd}
        FA & FB \\
        GA & GB
        \arrow["Ff", from=1-1, to=1-2]
        \arrow["{\alpha_A}", shift left=2, from=1-1, to=2-1]
        \arrow["Gf"', from=2-1, to=2-2]
        \arrow["{\alpha_B}"', shift right=2, from=1-2, to=2-2]
        \arrow["{\beta_B}"', shift right=2, from=2-2, to=1-2]
        \arrow["{\beta_A}", shift left=2, from=2-1, to=1-1]
    \end{tikzcd}\]
    Then
    \[ (Ff)\beta_A = \beta_B \alpha_B (Ff) \beta_A = \beta_B(Gf) \alpha_A \beta_A = \beta_B (Gf) \]
    using naturality of \( \alpha \).
    Thus \( \beta \) is natural, and an inverse for \( \alpha \).
\end{proof}
\begin{definition}
    Let \( \mathcal C, \mathcal D \) be categories.
    An \emph{equivalence} between \( \mathcal C \) and \( \mathcal D \) is a pair of functors
    \[ F : \mathcal C \to \mathcal D;\quad G : \mathcal D \to \mathcal C \]
    and a pair of natural isomorphisms
    \[ \alpha : 1_{\mathcal C} \to GF;\quad \beta : FG \to 1_{\mathcal D} \]
    If \( \mathcal C \) and \( \mathcal D \) are equivalent, we write \( \mathcal C \simeq \mathcal D \).
\end{definition}
The reason the natural isomorphisms point in opposite directions will be clarified later.
A property \( P \) of categories that is called \emph{categorical} if whenever \( \mathcal C \) satisfies \( P \) and \( \mathcal C \simeq \mathcal D \), then \( \mathcal D \) satisfies \( P \).
For example, the properties of being a preorder or being a groupoid are categorical.
Being a partial order or being a group are not categorical.
Generally, properties that rely on equality of objects, not isomorphism, will not be categorical.
\begin{example}
    \begin{enumerate}
        \item Let \( \mathbf{Set}_\star \) be the category of pointed sets and functions preserving the base point.
        Then \( \mathbf{Set}_\star \simeq \mathbf{Part} \) by
        \[ F : \mathbf{Set}_\star \to \mathbf{Part};\quad F(A, a) = A \setminus \qty{a};\quad F((A, a) \xrightarrow f (B, b))(x) = f(x) \]
        and
        \[ G : \mathbf{Part} \to \mathbf{Set}_\star;\quad G(A) = A \cup \qty{A};\quad G(A \xrightarrow f B \text{ partial})(x) = \begin{cases}
            f(x) & \text{if } f \text{ is defined at } x \\
            V & \text{otherwise}
        \end{cases} \]
        Note that \( FG = 1_{\mathbf{Part}} \), but \( GF \) is not equal to \( 1_{\mathbf{Set}_\star} \).
        It is not possible for these two categories to be isomorphic, because there is an isomorphism class of \( \mathbf{Part} \) that has only one member, namely \( \qty{\varnothing} \), but this cannot occur in \( \mathbf{Set}_\star \).
        \item Let \( \mathbf{fdVect}_k \) be the category of finite-dimensional vector spaces over \( k \).
        This category is equivalent to its opposite category \( \mathbf{fdVect}_k^\cop \) via the dual space functors in both directions.
        The natural isomorphisms \( \alpha \) and \( \beta \) are both as in the double dual example given above.
        \item We show \( \mathbf{fdVect}_k \simeq \mathbf{Mat}_k \).
        Define
        \[ F : \mathbf{Mat}_k \to \mathbf{fdVect}_k;\quad F(n) = k^n \]
        and sending a matrix \( A \) to the linear map it represents in the standard basis.
        For each finite-dimensional vector space \( V \), choose a particular basis.
        Define
        \[ G : \mathbf{fdVect}_k \to \mathbf{Mat}_k;\quad G(V) = \dim V \]
        and let \( G(\theta) \) be the matrix representing \( \theta \) with respect to the particular bases chosen above.
        Then \( GF = 1_{\mathbf{Mat}_k} \), as long as we chose the bases above in such a way that the \( k^n \) have the standard basis.
        Further, \( FG \) is naturally isomorphic to \( 1_{\mathbf{fdVect}_k} \), since the chosen bases define isomorphisms \( k^{\dim V} \to V \), which are natural in \( V \).
    \end{enumerate}
\end{example}
In line with the idea that we do not want to consider equality of objects but only equality of morphisms, we make the following definitions.
\begin{definition}
    Let \( F : \mathcal C \to \mathcal D \) be a functor.
    We say that \( F \) is
    \begin{enumerate}
        \item \emph{faithful}, if for each \( f, g \in \mor \mathcal C \) with equal domain and codomain, \( Ff = Fg \) implies \( f = g \);
        \item \emph{full}, if for each \( FA \xrightarrow g FB \), there exists a morphism \( A \xrightarrow f B \) such that \( Ff = g \);
        \item \emph{essentially surjective}, if every \( B \in \ob \mathcal D \) is isomorphic to some \( FA \) for \( A \in \ob \mathcal C \).
    \end{enumerate}
\end{definition}
Note that if \( F \) is full and faithful, it is \emph{essentially injective}: if \( FA \xrightarrow g FB \) is an isomorphism, the unique \( A \xrightarrow f B \) with \( Ff = g \) is an isomorphism, because its inverse is the unique \( B \to A \) mapped to \( g^{-1} \).
\begin{lemma}
    Let \( F : \mathcal C \to \mathcal D \) be a functor.
    Then \( F \) is part of an equivalence \( \mathcal C \simeq \mathcal D \) if and only if \( F \) is full, faithful, and essentially surjective.
\end{lemma}
\begin{proof}
    Suppose \( G, \alpha, \beta \) make \( F \) into an equivalence.
    The existence of \( \beta \) ensures that \( B \simeq FGB \) for any \( B \in \ob \mathcal D \), giving essential surjectivity.
    For faithfulness, for any \( A \xrightarrow f B \) in \( \mathcal C \), we have \( f = \alpha_B^{-1} (GFf) \alpha_A \), allowing us to reproduce \( f \) from its domain, codomain, and image under \( F \).
    For fullness, consider \( FA \xrightarrow g FB \), and define \( f = \alpha_B^{-1} (Gg) \alpha_A : A \to B \).
    Then, \( GFf = Gg \).
    As \( G \) is faithful by symmetry, \( Ff = g \).

    For the converse, for each object \( B \in \mathcal D \), we choose an isomorphism \( \beta_B : FA \to B \) where \( A \in \mathcal C \), and define the action of \( G \) at \( B \) to be this \( A \).
    Then we define \( G \) on morphisms by letting \( G(B \xrightarrow g C) \) be the unique \( GB \to GC \) whose image under \( F \) is \( \beta_C^{-1} \circ g \circ \beta_B \), thus making the following diagram commute.
    % https://q.uiver.app/#q=WzAsNCxbMCwwLCJGR0IiXSxbMCwxLCJCIl0sWzEsMSwiQyJdLFsxLDAsIkZHQyJdLFswLDEsIlxcYmV0YV9CIiwyXSxbMSwyLCJnIiwyXSxbMiwzLCJcXGJldGFfQ157LTF9IiwyXSxbMCwzLCJGR2ciXV0=
\[\begin{tikzcd}
	FGB & FGC \\
	B & C
	\arrow["{\beta_B}"', from=1-1, to=2-1]
	\arrow["g"', from=2-1, to=2-2]
	\arrow["{\beta_C^{-1}}"', from=2-2, to=1-2]
	\arrow["FGg", from=1-1, to=1-2]
\end{tikzcd}\]
    This is functorial: given \( h : C \to D \), we can form \( G(hg) \) and \( (Gh)(Gg) \) which have the same image under \( F \), so must be equal.
    % https://q.uiver.app/#q=WzAsNyxbMSwwLCJGR0IiXSxbMCwxLCJCIl0sWzEsMiwiQyJdLFsyLDEsIkZHQyJdLFszLDIsIkMiXSxbNCwxLCJEIl0sWzMsMCwiRkdEIl0sWzAsMSwiXFxiZXRhX0IiLDJdLFsxLDIsImciLDJdLFsyLDMsIlxcYmV0YV9DXnstMX0iXSxbMCwzLCJGR2ciLDJdLFszLDQsIlxcYmV0YV9DIl0sWzQsNSwiaCIsMl0sWzUsNiwiXFxiZXRhX0Reey0xfSIsMl0sWzMsNiwiRkdoIiwyXSxbMiw0LCIxX0MiLDJdLFswLDYsIkZHKGhnKSJdXQ==
\[\begin{tikzcd}
	& FGB && FGD \\
	B && FGC && D \\
	& C && C
	\arrow["{\beta_B}"', from=1-2, to=2-1]
	\arrow["g"', from=2-1, to=3-2]
	\arrow["{\beta_C^{-1}}", from=3-2, to=2-3]
	\arrow["FGg"', from=1-2, to=2-3]
	\arrow["{\beta_C}", from=2-3, to=3-4]
	\arrow["h"', from=3-4, to=2-5]
	\arrow["{\beta_D^{-1}}"', from=2-5, to=1-4]
	\arrow["FGh"', from=2-3, to=1-4]
	\arrow["{1_C}"', from=3-2, to=3-4]
	\arrow["{FG(hg)}", from=1-2, to=1-4]
\end{tikzcd}\]
    By construction, \( \beta \) is a natural isomorphism \( FG \to 1_{\mathcal D} \).
    It suffices to construct the natural isomorphism \( \alpha : 1_{\mathcal C} \to GF \).
    Its component at \( A \) is the unique isomorphism whose image under \( F \) is
    \[\begin{tikzcd}
        FA & FGFA
        \arrow["{\beta_{FA}^{-1}}", from=1-1, to=1-2]
    \end{tikzcd}\]
    Consider a naturality square for \( \alpha \).
    \[\begin{tikzcd}
        A & B \\
        GFA & GFB
        \arrow["f", from=1-1, to=1-2]
        \arrow["{\alpha_B}", from=1-2, to=2-2]
        \arrow["{\alpha_A}"', from=1-1, to=2-1]
        \arrow["GFf"', from=2-1, to=2-2]
    \end{tikzcd}\]
    As \( F \) is faithful, to show this diagram commutes, it suffices to show that its image under \( F \) commutes.
    \[\begin{tikzcd}
        FA & FB \\
        FGFA & FGFB
        \arrow["Ff", from=1-1, to=1-2]
        \arrow["{F\alpha_B = \beta_{FB}^{-1}}", from=1-2, to=2-2]
        \arrow["{F\alpha_A = \beta_{FA}^{-1}}"', from=1-1, to=2-1]
        \arrow["FGFf"', from=2-1, to=2-2]
    \end{tikzcd}\]
    This commutes by naturality of \( \beta^{-1} \).
\end{proof}
We call a subcategory full if its inclusion functor is full.
\begin{definition}
    A category of \emph{skeletal} if every isomorphism class has a single member.
    A \emph{skeleton} of \( \mathcal C \) is a full subcategory \( \mathcal C' \) containing exactly one object for each isomorphism class.
\end{definition}
Note that an equivalence of skeletal categories is bijective on objects, and hence is an isomorphism of categories.

\subsection{Monomorphisms and epimorphisms}
\begin{definition}
    A morphism \( f : A \to B \) is a \emph{monomorphism}, and is called \emph{monic}, if \( fg = fh \) implies \( g = h \) whenever the compositions are defined.
    Dually, \( f \) is an \emph{epimorphism}, and is called \emph{epic}, if \( gf = hf \) implies \( g = h \) whenever the compositions are defined.
\end{definition}
Monomorphisms are left-cancellable; epimorphisms are right-cancellable.
We will often denote a monomorphism with an arrow with a tail \( A \rightarrowtail B \), and denote epimorphisms with double-headed arrows \( A \twoheadrightarrow B \).
Isomorphisms are clearly monic and epic; if all monic and epic morphisms in a category are isomorphisms, we call the category \emph{balanced}.
\begin{example}
    \begin{enumerate}
        \item In \( \mathbf{Set} \), the monomorphisms are precisely the injective functions, and the epimorphisms are precisely the surjective functions.
        Thus \( \mathbf{Set} \) is balanced.
        % monic: maps from 1 correspond to elements; epic: consider maps to 2
        \item In \( \mathbf{Gp} \), the monomorphisms are the injective functions, and the epimorphisms are the surjective functions.
        % epic is hard; monic: consider maps from Z
        \item In \( \mathbf{Rng} \), the monomorphisms are again the injective functions, but there are epimorphisms that are not surjective, for example the inclusion \( \mathbb Z \to \mathbb Q \).
        \item In \( \mathbf{Top} \), the monomorphisms are the injective functions, and the epimorphisms are the surjective functions.
        However, \( \mathbf{Top} \) is not balanced, because continuous bijections need not have continuous inverses.
        \item In a preorder, any morphism is monic and epic.
        The category is balanced if and only if it is an equivalence relation (or equivalently, symmetric).
    \end{enumerate}
\end{example}
